package puzzle.projecteuler.p100;

public class Problem078A {

	private static long divisor = 1000000L;
	/**
	 * 
	 * 参考： http://pign.net/index.php?hl=f5&q=uggc%3A%2F%2Fra.jvxvcrqvn.bet%2Fjvxv%2FCnegvgvba_(ahzore_gurbel)
	 * p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22)...
	 * 其中1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51...是五边形数（n(3n-1)/2）中n=1,-1,2,-2,3,-3,...对应的值
	 * p(0)=1, p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, ...
	 * 
	 * 与Problem076比较
	 * @param args
	 */
	public static void main(String[] args) {
		long s = System.currentTimeMillis();
		long[] ps = ps(60000);
		for (int i = 0; i < ps.length; i ++) {
			if (ps[i] == 0) {
				System.out.println(i);
				break;
			}
		}
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	public static long[] ps(int n) {
		if (n < 5) {
			throw new RuntimeException();
		} else {
			long[] p = new long[n+1];
			p[0] = 1;
			p[1] = 1;
			p[2] = 2;
			p[3] = 3;
			p[4] = 5;
			for (int i = 5; i < p.length; i ++) {
				long v = 0;
				int j = 1;
				int t = (j+1)/2;
				int s = t*(3*t-1)/2;
				while (s <= i) {
					if (j%4 == 1 || j%4 == 2) {
						v += p[i-s];
					} else {
						v -= p[i-s];
					}
					v %= divisor; 
					j ++;
					t = (j+1)/2;
					s = (j%2==1)?t*(3*t-1)/2:t*(3*t+1)/2;
				}
				p[i] = v;
			}
			return p;
		}
	}
}
